package daily.jun0627;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Set;

//计算组合数的类
class CombinationNumberCalculation {
    public static int[] factor(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("N must be a non negative integer.");
        }
        if (n < 4) {
            return new int[]{n};
        }
        int factorNums = (int) (Math.log(Integer.highestOneBit(n)) / Math.log(2));
        int[] factors = new int[factorNums];
        int factorCount = 0;
        for (int i = 2; i <= (int) Math.sqrt(n); i++) {
            if (n % i == 0) {
                factors[factorCount++] = i;
                n /= i;
                i = 1;
            }
        }
        factors[factorCount++] = n;
        return Arrays.copyOf(factors, factorCount);
    }

    public static long nchoosek(int n, int k) {
        if (n > 70 || (n == 70 && k > 25 && k < 45)) {
            throw new IllegalArgumentException("N(" + n + ") and k(" + k + ") don't meet the requirements.");
        }
        k = k > (n - k) ? n - k : k;
        if (k <= 1) {  // C(n, 0) = 1, C(n, 1) = n
            return k == 0 ? 1 : n;
        }
        int[] divisors = new int[k]; // n - k + 1 : n
        int firstDivisor = n - k + 1;
        for (int i = 0; i < k; i++) {
            divisors[i] = firstDivisor + i;
        }
        outer:
        for (int dividend = 2; dividend <= k; dividend++) {
            for (int i = k - 1; i >= 0; i--) {
                int divisor = divisors[i];
                if (divisor % dividend == 0) {
                    divisors[i] = divisor / dividend;
                    continue outer;
                }
            }
            int[] perms = factor(dividend);
            for (int perm : perms) {
                for (int j = 0; j < k; j++) {
                    int divisor = divisors[j];
                    if (divisor % perm == 0) {
                        divisors[j] = divisor / perm;
                        break;
                    }
                }
            }
        }
        long cnk = 1L;
        for (int i = 0; i < k; i++) {
            cnk *= divisors[i];
        }
        return cnk;
    }
}

class JerryProblem {
    private static StringBuilder groupA = new StringBuilder();//A组
    private static StringBuilder groupB = new StringBuilder();//B组
    private static long count = 0L;//初始化满足题意的个数

    private static void DFS(StringBuilder builder, int index, HashMap<Character, Integer> map, HashMap<Character, Integer> copiedMap) {
        //builder:传入的字符串
        //index:角标，用于取出字符
        //二叉树：每一个字符是一层
        //伪算法如下：
        //向字符串a中加入字符
        //DFS(left)
        //向字符串a中减去字符，向b中加入字符
        //DFS(right)
        //return
        //进一步筛选退出：
        //如果a的第一个字符的角标大于n-1，退出
        //选定所有字符之后，如果不符合比较的条件，退出
        //选完所有字符之后，如果字符串a的大小小于n，退出方法

        if (index > builder.length() - 1) {
            //来到这一步说明A组字符串第一个角标已经大于n-1
            if (groupA.length() < builder.length() / 2) {
                return;
            }
        }
        //如果恰好遍历完时有合法序列形成，则不返回，执行下面的代码
        if (groupA.length() >= builder.length() / 2) {
            //合法序列形成，index以及之后的字符要全部加入到groupB中
            int strEnd = groupB.length();
            for (int i = index; i < builder.length(); i++) {
                char ch = builder.charAt(i);
                groupB.append(ch);
            }
            //此时如果A组和反转后的B组相同，则count加1
            if (groupA.toString().equals(groupB.reverse().toString())) {
                count++;
            }
            //将B串反转回来，然后清理B字符串
            groupB.reverse();
            groupB.delete(strEnd, groupB.length());
            return;
        }
        char ch = builder.charAt(index);//获取当前处理的字符
        int countAlphabet = copiedMap.get(ch);
        groupA.append(ch);
        if (countAlphabet > map.get(ch) / 2) {
            //合法字符，向左子树遍历
            copiedMap.put(ch, --countAlphabet);//用过之后当前字母对应的value要减去1
            DFS(builder, index + 1, map, copiedMap);
        } else {
            copiedMap.put(ch, --countAlphabet);//用过之后当前字母对应的value要减去1
        }
        groupA.deleteCharAt(groupA.length() - 1);//删除末尾字符
        copiedMap.put(ch, ++countAlphabet);//加回来
        //遍历右子树
        if (index < builder.length() - 1) {
            groupB.append(ch);
            DFS(builder, index + 1, map, copiedMap);
            groupB.deleteCharAt(groupB.length() - 1);//删除末尾字符
            return;
        }
        //如果指针已经到末尾了，就不需要遍历了，返回
        return;
    }

    public static long solution(int n, String s) {
        //创建一个StringBuilder容器
        StringBuilder builder = new StringBuilder();
        //将传入的字符串s添加到容器中
        builder.append(s);
        //因为key不能重复，因此用于统计字符串中出现了的字母，value统计这个字母出现的次数
        HashMap<Character, Integer> map = new HashMap<>();
        //遍历字符串，统计字符串中每一种字母出现的次数
        for (int i = 0; i < 2 * n; i++) {
            char c = builder.charAt(i);//逐个扫描字符
            int countAlphabet = 0;//统计同一个字母出现次数，作为HashMap中key对应的value，初始化为0
            //如果map中已经存储了当前扫描到的字母了，就直接把其对应的value赋值给countAlphabet
            if (map.containsKey(c)) {
                countAlphabet = map.get(c);
            }
            //将当前正在扫描到的字母添加到map中，由于key不能重复，如果map中已经存在了当前字母，则只增加value
            map.put(c, ++countAlphabet);
        }
        //System.out.println(map);//测试一下统计出来正不正确

        //如果出现某个字母只有奇数个，则此题无解，直接返回0
        Set<Character> set = map.keySet();//把所有的键放到集合中
        for (Character key : set) {
            //如果有任何一个键对应的值不等于0，就返回0
            if (map.get(key) % 2 != 0) {
                return 0;
            }
        }

        //如果传入的字符串只有一个字母，则进行排列组合，公式为C(2n,n),上面写好了相关函数
        if (1 == map.size()) {
            count = CombinationNumberCalculation.nchoosek(2 * n, n);
            return count;
        }

        //拷贝刚刚统计好的集合map到一个新的集合中，用于记录字符的使用情况
        HashMap<Character, Integer> copiedMap = new HashMap<>();
        copiedMap.putAll(map);//putAll方法将map集合的键值对复制到新的集合

        //调用DFS算法
        DFS(builder, 0, map, copiedMap);
        return count;
    }
}

public class JerryProblemTest {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        String str = "qqnaxhchvdjjdvhchxanqq";
        System.out.println(JerryProblem.solution(str.length() / 2, str));
        long endTime = System.currentTimeMillis();
        System.out.printf("运行时间：%d毫秒", endTime - startTime);
    }
}
